package LeetCode;

import TimeCounter.CglibProxy;

/**
 * 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
 *
 * 输入：l1 = [1,2,4], l2 = [1,3,4]
 * 输出：[1,1,2,3,4,4]
 * 示例 2：
 *
 * 输入：l1 = [], l2 = []
 * 输出：[]
 * 示例 3：
 *
 * 输入：l1 = [], l2 = [0]
 * 输出：[0]
 *  
 *
 * 提示：
 *
 * 两个链表的节点数目范围是 [0, 50]
 * -100 <= Node.val <= 100
 * l1 和 l2 均按 非递减顺序 排列
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/merge-two-sorted-lists
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Code21 {
    private static class ListNode{
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) { // 第一种迭代法， 不要忘记操作链表，最少两个指针
        ListNode answerList = new ListNode();
        ListNode currentP = answerList;
        while (l1 != null || l2 != null){ // 每次比较两个点的值，考虑到有可能出现空的情况
            int a = l1 != null ? l1.val : 101;
            int b = l2 != null ? l2.val : 101;
            if (a <= b){
                currentP.val = a;
                l1 = l1 != null? l1.next : null;
            }else {
                currentP.val = b;
                l2 = l2 != null? l2.next : null;
            }
            System.out.println("answerList -->" + currentP.val);
            if (l1 == null && l2 == null)
                return answerList;
            currentP.next = new ListNode();
            currentP = currentP.next;
        }
        return null;
    }

    public ListNode mergeTwoLists2(ListNode l1, ListNode l2) { // 第二种方法，递归

        return run(l1,l2);
    }

    public ListNode run(ListNode l1, ListNode l2){ // 这里的想法还是，最后的结果是每次相加出来的。
        if (l1 == null && l2 == null)
            return null;
        int a = l1 != null ? l1.val : 101;
        int b = l2 != null ? l2.val : 101;
        ListNode answerList = new ListNode();
        if (a <= b){
            answerList.val = a;
            l1 = l1 != null? l1.next : null;
        }else {
            answerList.val = b;
            l2 = l2 != null? l2.next : null;
        }
        System.out.print("answerList = " + answerList.val);
        answerList.next = run(l1,l2);
        return answerList;
    }

    public static void main(String[] args) {
        Code21 proxy = new CglibProxy<Code21>().createProxy(new Code21());
        proxy.mergeTwoLists(new ListNode(1,new ListNode(2,new ListNode(4))),new ListNode(1,new ListNode(3,new ListNode(4))));
        proxy.mergeTwoLists2(new ListNode(1,new ListNode(2,new ListNode(4))),new ListNode(1,new ListNode(3,new ListNode(4))));
        proxy.mergeTwoLists(null,null);
        proxy.mergeTwoLists2(null,null);
        proxy.mergeTwoLists(null,new ListNode());
        proxy.mergeTwoLists2(null,new ListNode());
    }
}
